Search Results

Documents authored by Kayal, Neeraj

Document
DOI: 10.4230/LIPIcs.ITCS.2024.25
Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning

Authors: Pritam Chandra, Ankit Garg, Neeraj Kayal, Kunal Mittal, and Tanmay Sinha

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We present a general framework for designing efficient algorithms for unsupervised learning problems, such as mixtures of Gaussians and subspace clustering. Our framework is based on a meta algorithm that learns arithmetic formulas in the presence of noise, using lower bounds. This builds upon the recent work of Garg, Kayal and Saha (FOCS '20), who designed such a framework for learning arithmetic formulas without any noise. A key ingredient of our meta algorithm is an efficient algorithm for a novel problem called Robust Vector Space Decomposition. We show that our meta algorithm works well when certain matrices have sufficiently large smallest non-zero singular values. We conjecture that this condition holds for smoothed instances of our problems, and thus our framework would yield efficient algorithms for these problems in the smoothed setting.
Cite as

Pritam Chandra, Ankit Garg, Neeraj Kayal, Kunal Mittal, and Tanmay Sinha. Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 25:1-25:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chandra_et_al:LIPIcs.ITCS.2024.25,
  author =	{Chandra, Pritam and Garg, Ankit and Kayal, Neeraj and Mittal, Kunal and Sinha, Tanmay},
  title =	{{Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{25:1--25:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.25},
  URN =		{urn:nbn:de:0030-drops-195537},
  doi =		{10.4230/LIPIcs.ITCS.2024.25},
  annote =	{Keywords: Arithmetic Circuits, Robust Vector Space Decomposition, Subspace Clustering, Mixtures of Gaussians}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.12
Low-Depth Arithmetic Circuit Lower Bounds: Bypassing Set-Multilinearization

Authors: Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, and Bhargav Thankey

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
A recent breakthrough work of Limaye, Srinivasan and Tavenas [Nutan Limaye et al., 2021] proved superpolynomial lower bounds for low-depth arithmetic circuits via a "hardness escalation" approach: they proved lower bounds for low-depth set-multilinear circuits and then lifted the bounds to low-depth general circuits. In this work, we prove superpolynomial lower bounds for low-depth circuits by bypassing the hardness escalation, i.e., the set-multilinearization, step. As set-multilinearization comes with an exponential blow-up in circuit size, our direct proof opens up the possibility of proving an exponential lower bound for low-depth homogeneous circuits by evading a crucial bottleneck. Our bounds hold for the iterated matrix multiplication and the Nisan-Wigderson design polynomials. We also define a subclass of unrestricted depth homogeneous formulas which we call unique parse tree (UPT) formulas, and prove superpolynomial lower bounds for these. This significantly generalizes the superpolynomial lower bounds for regular formulas [Neeraj Kayal et al., 2014; Hervé Fournier et al., 2015].
Cite as

Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, and Bhargav Thankey. Low-Depth Arithmetic Circuit Lower Bounds: Bypassing Set-Multilinearization. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{amireddy_et_al:LIPIcs.ICALP.2023.12,
  author =	{Amireddy, Prashanth and Garg, Ankit and Kayal, Neeraj and Saha, Chandan and Thankey, Bhargav},
  title =	{{Low-Depth Arithmetic Circuit Lower Bounds: Bypassing Set-Multilinearization}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{12:1--12:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.12},
  URN =		{urn:nbn:de:0030-drops-180642},
  doi =		{10.4230/LIPIcs.ICALP.2023.12},
  annote =	{Keywords: arithmetic circuits, low-depth circuits, lower bounds, shifted partials}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.21
Learning Generalized Depth Three Arithmetic Circuits in the Non-Degenerate Case

Authors: Vishwas Bhargava, Ankit Garg, Neeraj Kayal, and Chandan Saha

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract
Consider a homogeneous degree d polynomial f = T₁ + ⋯ + T_s, T_i = g_i(𝓁_{i,1}, …, 𝓁_{i, m}) where g_i’s are homogeneous m-variate degree d polynomials and 𝓁_{i,j}’s are linear polynomials in n variables. We design a (randomized) learning algorithm that given black-box access to f, computes black-boxes for the T_i’s. The running time of the algorithm is poly(n, m, d, s) and the algorithm works under some non-degeneracy conditions on the linear forms and the g_i’s, and some additional technical assumptions n ≥ (md)², s ≤ n^{d/4}. The non-degeneracy conditions on 𝓁_{i,j}’s constitute non-membership in a variety, and hence are satisfied when the coefficients of 𝓁_{i,j}’s are chosen uniformly and randomly from a large enough set. The conditions on g_i’s are satisfied for random polynomials and also for natural polynomials common in the study of arithmetic complexity like determinant, permanent, elementary symmetric polynomial, iterated matrix multiplication. A particularly appealing algorithmic corollary is the following: Given black-box access to an f = Det_r(L^(1)) + … + Det_r(L^(s)), where L^(k) = (𝓁_{i,j}^(k))_{i,j} with 𝓁_{i,j}^(k)’s being linear forms in n variables chosen randomly, there is an algorithm which in time poly(n, r) outputs matrices (M^(k))_k of linear forms s.t. there exists a permutation π: [s] → [s] with Det_r(M^(k)) = Det_r(L^(π(k))). Our work follows the works [Neeraj Kayal and Chandan Saha, 2019; Garg et al., 2020] which use lower bound methods in arithmetic complexity to design average case learning algorithms. It also vastly generalizes the result in [Neeraj Kayal and Chandan Saha, 2019] about learning depth three circuits, which is a special case where each g_i is just a monomial. At the core of our algorithm is the partial derivative method which can be used to prove lower bounds for generalized depth three circuits. To apply the general framework in [Neeraj Kayal and Chandan Saha, 2019; Garg et al., 2020], we need to establish that the non-degeneracy conditions arising out of applying the framework with the partial derivative method are satisfied in the random case. We develop simple but general and powerful tools to establish this, which might be useful in designing average case learning algorithms for other arithmetic circuit models.
Cite as

Vishwas Bhargava, Ankit Garg, Neeraj Kayal, and Chandan Saha. Learning Generalized Depth Three Arithmetic Circuits in the Non-Degenerate Case. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 21:1-21:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bhargava_et_al:LIPIcs.APPROX/RANDOM.2022.21,
  author =	{Bhargava, Vishwas and Garg, Ankit and Kayal, Neeraj and Saha, Chandan},
  title =	{{Learning Generalized Depth Three Arithmetic Circuits in the Non-Degenerate Case}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{21:1--21:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.21},
  URN =		{urn:nbn:de:0030-drops-171430},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.21},
  annote =	{Keywords: Arithemtic Circuits, Average-case Learning, Depth 3 Arithmetic Circuits, Learning Algorithms, Learning Circuits, Circuit Reconstruction}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.62
Determinant Equivalence Test over Finite Fields and over Q

Authors: Ankit Garg, Nikhil Gupta, Neeraj Kayal, and Chandan Saha

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
The determinant polynomial Det_n(x) of degree n is the determinant of a n x n matrix of formal variables. A polynomial f is equivalent to Det_n(x) over a field F if there exists a A in GL(n^2,F) such that f = Det_n(A * x). Determinant equivalence test over F is the following algorithmic task: Given black-box access to a f in F[x], check if f is equivalent to Det_n(x) over F, and if so then output a transformation matrix A in GL(n^2,F). In (Kayal, STOC 2012), a randomized polynomial time determinant equivalence test was given over F = C. But, to our knowledge, the complexity of the problem over finite fields and over Q was not well understood. In this work, we give a randomized poly(n,log |F|) time determinant equivalence test over finite fields F (under mild restrictions on the characteristic and size of F). Over Q, we give an efficient randomized reduction from factoring square-free integers to determinant equivalence test for quadratic forms (i.e. the n=2 case), assuming GRH. This shows that designing a polynomial-time determinant equivalence test over Q is a challenging task. Nevertheless, we show that determinant equivalence test over Q is decidable: For bounded n, there is a randomized polynomial-time determinant equivalence test over Q with access to an oracle for integer factoring. Moreover, for any n, there is a randomized polynomial-time algorithm that takes input black-box access to a f in Q[x] and if f is equivalent to Det_n over Q then it returns a A in GL(n^2,L) such that f = Det_n(A * x), where L is an extension field of Q and [L : Q] <= n. The above algorithms over finite fields and over Q are obtained by giving a polynomial-time randomized reduction from determinant equivalence test to another problem, namely the full matrix algebra isomorphism problem. We also show a reduction in the converse direction which is efficient if n is bounded. These reductions, which hold over any F (under mild restrictions on the characteristic and size of F), establish a close connection between the complexity of the two problems. This then leads to our results via applications of known results on the full algebra isomorphism problem over finite fields (Rónyai, STOC 1987 and Rónyai, J. Symb. Comput. 1990) and over Q (Ivanyos {et al}., Journal of Algebra 2012 and Babai {et al}., Mathematics of Computation 1990).
Cite as

Ankit Garg, Nikhil Gupta, Neeraj Kayal, and Chandan Saha. Determinant Equivalence Test over Finite Fields and over Q. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 62:1-62:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.ICALP.2019.62,
  author =	{Garg, Ankit and Gupta, Nikhil and Kayal, Neeraj and Saha, Chandan},
  title =	{{Determinant Equivalence Test over Finite Fields and over Q}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{62:1--62:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.62},
  URN =		{urn:nbn:de:0030-drops-106382},
  doi =		{10.4230/LIPIcs.ICALP.2019.62},
  annote =	{Keywords: Determinant equivalence test, full matrix algebra isomorphism, Lie algebra}
}
Document
DOI: 10.4230/LIPIcs.CCC.2017.21
Reconstruction of Full Rank Algebraic Branching Programs

Authors: Neeraj Kayal, Vineet Nair, Chandan Saha, and Sébastien Tavenas

Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)

Abstract
An algebraic branching program (ABP) A can be modelled as a product expression X_1 X_2 ... X_d, where X_1 and X_d are 1 x w and w x 1 matrices respectively, and every other X_k is a w x w matrix; the entries of these matrices are linear forms in m variables over a field F (which we assume to be either Q or a field of characteristic poly(m)). The polynomial computed by A is the entry of the 1 x 1 matrix obtained from the product X_1 X_2 ... X_d. We say A is a full rank ABP if the w^2(d-2) + 2w linear forms occurring in the matrices X_1, X_2, ... , X_d are F-linearly independent. Our main result is a randomized reconstruction algorithm for full rank ABPs: Given blackbox access to an m-variate polynomial f of degree at most m, the algorithm outputs a full rank ABP computing f if such an ABP exists, or outputs 'no full rank ABP exists' (with high probability). The running time of the algorithm is polynomial in m and b, where b is the bit length of the coefficients of f. The algorithm works even if X_k is a w_{k-1} x w_k matrix (with w_0 = w_d = 1), and v = (w_1, ..., w_{d-1}) is unknown. The result is obtained by designing a randomized polynomial time equivalence test for the family of iterated matrix multiplication polynomial IMM_{v,d}, the (1,1)-th entry of a product of d rectangular symbolic matrices whose dimensions are according to v in N^{d-1}. At its core, the algorithm exploits a connection between the irreducible invariant subspaces of the Lie algebra of the group of symmetries of a polynomial f that is equivalent to IMM_{v,d} and the 'layer spaces' of a full rank ABP computing f. This connection also helps determine the group of symmetries of IMM_{v,d} and show that IMM_{v,d} is characterized by its group of symmetries.
Cite as

Neeraj Kayal, Vineet Nair, Chandan Saha, and Sébastien Tavenas. Reconstruction of Full Rank Algebraic Branching Programs. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 21:1-21:61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kayal_et_al:LIPIcs.CCC.2017.21,
  author =	{Kayal, Neeraj and Nair, Vineet and Saha, Chandan and Tavenas, S\'{e}bastien},
  title =	{{Reconstruction of Full Rank Algebraic Branching Programs}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{21:1--21:61},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{O'Donnell, Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.21},
  URN =		{urn:nbn:de:0030-drops-75318},
  doi =		{10.4230/LIPIcs.CCC.2017.21},
  annote =	{Keywords: Circuit reconstruction, algebraic branching programs, equivalence test, iterated matrix multiplication, Lie algebra}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.33
An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits

Authors: Neeraj Kayal, Chandan Saha, and Sébastien Tavenas

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We show an almost cubic lower bound on the size of any depth three arithmetic circuit computing an explicit multilinear polynomial in n variables over any field. This improves upon the previously known quadratic lower bound by Shpilka and Wigderson [CCC, 1999].
Cite as

Neeraj Kayal, Chandan Saha, and Sébastien Tavenas. An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kayal_et_al:LIPIcs.ICALP.2016.33,
  author =	{Kayal, Neeraj and Saha, Chandan and Tavenas, S\'{e}bastien},
  title =	{{An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{33:1--33:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.33},
  URN =		{urn:nbn:de:0030-drops-63126},
  doi =		{10.4230/LIPIcs.ICALP.2016.33},
  annote =	{Keywords: arithmetic circuits, depth-3 circuits, shifted partials}
}
Document
DOI: 10.4230/LIPIcs.STACS.2016.46
Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits

Authors: Neeraj Kayal, Vineet Nair, and Chandan Saha

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract
We show an exponential separation between two well-studied models of algebraic computation, namely read-once oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits. In particular we show the following: 1. There exists an explicit n-variate polynomial computable by linear sized multilinear depth three circuits (with only two product gates) such that every ROABP computing it requires 2^{Omega(n)} size. 2. Any multilinear depth three circuit computing IMM_{n,d} (the iterated matrix multiplication polynomial formed by multiplying d, n * n symbolic matrices) has n^{Omega(d)} size. IMM_{n,d} can be easily computed by a poly(n,d) sized ROABP. 3. Further, the proof of 2 yields an exponential separation between multilinear depth four and multilinear depth three circuits: There is an explicit n-variate, degree d polynomial computable by a poly(n,d) sized multilinear depth four circuit such that any multilinear depth three circuit computing it has size n^{Omega(d)}. This improves upon the quasi-polynomial separation result by Raz and Yehudayoff [2009] between these two models. The hard polynomial in 1 is constructed using a novel application of expander graphs in conjunction with the evaluation dimension measure used previously in Nisan [1991], Raz [2006,2009], Raz and Yehudayoff [2009], and Forbes and Shpilka [2013], while 2 is proved via a new adaptation of the dimension of the partial derivatives measure used by Nisan and Wigderson [1997]. Our lower bounds hold over any field.
Cite as

Neeraj Kayal, Vineet Nair, and Chandan Saha. Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 46:1-46:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kayal_et_al:LIPIcs.STACS.2016.46,
  author =	{Kayal, Neeraj and Nair, Vineet and Saha, Chandan},
  title =	{{Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{46:1--46:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.46},
  URN =		{urn:nbn:de:0030-drops-57475},
  doi =		{10.4230/LIPIcs.STACS.2016.46},
  annote =	{Keywords: multilinear depth three circuits, read-once oblivious algebraic branching programs, evaluation dimension, skewed partial derivatives, expander graphs,}
}
Document
DOI: 10.4230/LIPIcs.CCC.2015.158
Lower Bounds for Depth Three Arithmetic Circuits with Small Bottom Fanin

Authors: Neeraj Kayal and Chandan Saha

Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)

Abstract
Shpilka and Wigderson (CCC 99) had posed the problem of proving exponential lower bounds for (nonhomogeneous) depth three arithmetic circuits with bounded bottom fanin over a field F of characteristic zero. We resolve this problem by proving a N^(Omega(d/t)) lower bound for (nonhomogeneous) depth three arithmetic circuits with bottom fanin at most t computing an explicit N-variate polynomial of degree d over F. Meanwhile, Nisan and Wigderson (CC 97) had posed the problem of proving superpolynomial lower bounds for homogeneous depth five arithmetic circuits. Over fields of characteristic zero, we show a lower bound of N^(Omega(sqrt(d))) for homogeneous depth five circuits (resp. also for depth three circuits) with bottom fanin at most N^(u), for any fixed u < 1. This resolves the problem posed by Nisan and Wigderson only partially because of the added restriction on the bottom fanin (a general homogeneous depth five circuit has bottom fanin at most N).
Cite as

Neeraj Kayal and Chandan Saha. Lower Bounds for Depth Three Arithmetic Circuits with Small Bottom Fanin. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 158-182, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{kayal_et_al:LIPIcs.CCC.2015.158,
  author =	{Kayal, Neeraj and Saha, Chandan},
  title =	{{Lower Bounds for Depth Three Arithmetic Circuits with Small Bottom Fanin}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{158--182},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{Zuckerman, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.158},
  URN =		{urn:nbn:de:0030-drops-50617},
  doi =		{10.4230/LIPIcs.CCC.2015.158},
  annote =	{Keywords: arithmetic circuits, depth three circuits, lower bound, bottom fanin}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.527
Multi-k-ic Depth Three Circuit Lower Bound

Authors: Neeraj Kayal and Chandan Saha

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
In a multi-k-ic depth three circuit every variable appears in at most k of the linear polynomials in every product gate of the circuit. This model is a natural generalization of multilinear depth three circuits that allows the formal degree of the circuit to exceed the number of underlying variables (as the formal degree of a multi-k-ic depth three circuit can be kn where n is the number of variables). The problem of proving lower bounds for depth three circuits with high formal degree has gained in importance following a work by Gupta, Kamath, Kayal and Saptharishi [7] on depth reduction to high formal degree depth three circuits. In this work, we show an exponential lower bound for multi-k-ic depth three circuits for any arbitrary constant k.
Cite as

Neeraj Kayal and Chandan Saha. Multi-k-ic Depth Three Circuit Lower Bound. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 527-539, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{kayal_et_al:LIPIcs.STACS.2015.527,
  author =	{Kayal, Neeraj and Saha, Chandan},
  title =	{{Multi-k-ic Depth Three Circuit Lower Bound}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{527--539},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.527},
  URN =		{urn:nbn:de:0030-drops-49395},
  doi =		{10.4230/LIPIcs.STACS.2015.527},
  annote =	{Keywords: arithmetic circuits, multilinear circuits, depth three circuits, lower bound, individual degree}
}
Document
Tutorial
DOI: 10.4230/LIPIcs.STACS.2014.28
Arithmetic Circuit Complexity (Tutorial)

Authors: Neeraj Kayal

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
Arithmetic Circuits compute polynomial functions over their inputs via a sequence of arithmetic operations (additions, subtractions, multiplications, divisions, etc.). This tutorial will give an overview of arithmetic circuit complexity, focusing on the problem of proving lower bounds for arithmetic circuits. In the first part, we begin with a few nontrivial upper bounds - matrix multiplication and the computation of symmetric polynomials. We then motivate some open problems we deal with in arithmetic circuit complexity. We will look at the problem of polynomial identity testing - motivating it by its application to bipartite matching, the problem of learning arithmetic circuits or circuit reconstruction and the problem of proving lower bounds for arithmetic circuits (motivating it via the problem of computing the permanent and the Hamiltonian polynomials). We will also see depth reduction for circuits - the tradeoffs involved (with respect to size) in squashing a circuit into one with smaller depth. In the second part, we will see some classical lower bounds. In particular, we will see lower bounds for monotone arithmetic circuits and multilinear formulas. We then give a very quick overview of approaches being investigated (including geometric complexity theory and tau-conjecture) aiming to prove lower bounds. In the third part, we begin with a warm-up by proving lower bounds for homogeneous depth three circuits. We will then see recent lower bounds for homogeneous depth four circuits and its consequences.
Cite as

Neeraj Kayal. Arithmetic Circuit Complexity (Tutorial). In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, p. 28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{kayal:LIPIcs.STACS.2014.28,
  author =	{Kayal, Neeraj},
  title =	{{Arithmetic Circuit Complexity}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{28--28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.28},
  URN =		{urn:nbn:de:0030-drops-45012},
  doi =		{10.4230/LIPIcs.STACS.2014.28},
  annote =	{Keywords: Circuit complexity, arithmetic circuits, lower bounds, polynomial identity testing}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact